package array.removeelement;

import java.util.Stack;

/**
 * @ClassName BackSpaceCompare
 * @Description TODO
 * @Author lenovo
 * @Date 2023-02-10 14:45
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class BackSpaceCompare {

    /**
     * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
     * <p>
     * 注意：如果对空文本输入退格字符，文本继续为空。
     * 示例 1：
     * <p>
     * 输入：s = “ab#c”, t = “ad#c”
     * 输出：true
     * 解释：s 和 t 都会变成 “ac”。
     * <p>
     * 示例 2：
     * <p>
     * 输入：s = “ab##”, t = “c#d#”
     * 输出：true
     * 解释：s 和 t 都会变成 “”。
     * <p>
     * 示例 3：
     * <p>
     * 输入：s = “a#c”, t = “b”
     * 输出：false
     * 解释：s 会变成 “c”，但 t 仍然是 “b”。
     * <p>
     * 提示：
     * 1 <= s.length, t.length <= 200
     * s 和 t 只含有小写字母以及字符 ‘#’
     *
     * @param s
     * @param t
     * @return
     */
    public static boolean backSpaceCompare(String s, String t) {
        //使用栈的方式来存储'#'
        Stack<Character> stack1 = new Stack<Character>();
        Stack<Character> stack2 = new Stack<Character>();
        int n1 = s.length();
        for (int i = 0; i < n1; i++) {
            char c = s.charAt(i);
            //如果字符不是#的话，那么就直接push进栈里面，
            //如果是#的话，相当于是个删除，需要把之前的字符给弹出来
            if (c != '#') {
                stack1.push(c);
            } else {
                if (!stack1.isEmpty()) {
                    stack1.pop();
                }
            }
        }

        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (c != '#') {
                stack2.push(c);
            } else {
                if (!stack2.isEmpty()) {
                    stack2.pop();
                }
            }
        }
        boolean res = true;
        if (stack1.size() != stack2.size()) {
            return false;
        } else {
            while (!stack1.isEmpty()) {
                Character pop1 = stack1.pop();
                Character pop2 = stack2.pop();
                if (pop1 != pop2) {
                    res = false;
                }
            }
        }
        return res;
    }

    public static boolean backspaceCompare1(String s, String t) {

        int sLen = s.length() - 1;
        int tLen = t.length() - 1;

        while (sLen >= 0 || tLen >= 0) {
            //跳过'#'字符的标记
            int skp1 = 0, skp2 = 0;

            while (sLen >= 0) {
                if (s.charAt(sLen) == '#') { //当字符等于#的时候，那么跳过
                    skp1++;
                    sLen--;
                } else if (skp1 > 0) { //因为字符#相当于删除字符，所以把前面的字符删掉
                    skp1--;
                    sLen--;
                } else {
                    break;
                }
            }

            while (tLen >= 0) {
                if (t.charAt(tLen) == '#') {
                    skp2++;
                    tLen--;
                } else if (skp2 > 0) {
                    skp2--;
                    tLen--;
                } else {
                    break;
                }
            }

            if (sLen >= 0 && tLen >= 0) {
                if (s.charAt(sLen) == t.charAt(tLen)) {
                    sLen--;
                    tLen--;
                } else {
                    return false;
                }
            } else {
                if (sLen >= 0 || tLen >= 0) {
                    return false;
                }
            }
        }
        return true;

    }

    public static void main(String args[]) {

        System.out.println(backspaceCompare1("ab##c", "5ad##c"));

    }
}